package com.smh.a02PaiXuDemo2;

import java.util.Random;

public class KuaiSuPaiXu {
    public static void main(String[] args) {
        int[] arr = {12, 34, 51, 21, 23, 12, 32, 43, 12, 3, 234, 2};
        kuaipai(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();

        int[] arr2 = new int[10000];
        Random random = new Random();
        for (int i = 0; i < arr2.length; i++) {
            arr2[i]=random.nextInt();
        }
        Long start = System.currentTimeMillis();
        kuaipai(arr2,0,arr2.length-1);
        Long end = System.currentTimeMillis();
        System.out.println(end-start);


    }

    public static void kuaipai(int[] arr, int i, int j) {
        int start = i;
        int end = j;
        if (start>end){
            return;
        }
        int baseNum = arr[i];
        while (start != end) {
            while (true) {
                if (end<=start||arr[end]<baseNum){
                    break;
                }
                end--;
            }
            while (true) {
                if (start>=end||arr[start]>baseNum){
                    break;
                }
                start++;
            }
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        kuaipai(arr,i,start-1);
        kuaipai(arr,start+1,j);
    }
}
